package com.ydc.ln.tutorial.algorithm;

import org.junit.Test;

/**
 * 算法小全 之 数论算法
 * 
 * <pre>
 * 1.求两数的最大公约数
 * 2.求两数的最小公倍数
 * 3.素数的求法
 * </pre>
 * 
 * @author yangdc
 * 
 */
public class Algorithm01 {

	@Test
	public void testPrint() {
		String primes = "";
	}
	
	@Test
	public void testGcd() {
		int result = gcd(15, 90);
		System.out.println(result);
	}

	@Test
	public void testLcm() {
		int result = lcm(15, 90);
		System.out.println(result);
	}

	@Test
	public void testIsPrime() {
		int count = 0;
		for (int i = 2; i < 15000; i++) {
			if (isPrime(i)) {
				count++;
				System.out.print(i + "\t");
				if (count % 10 == 0) {
					System.out.println();
				}
			}
			
		}
		System.out.println("\n" + count);
	}

	/**
	 * 求两个数的最大公约数
	 * 
	 * <pre>
	 * 如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。
	 * 几个自然数公有的约数，叫做这几个自然数的公约数。
	 * 公约数中最大的一个公约数，称为这几个自然数的最大公约数。 
	 * 
	 * </pre>
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public int gcd(int a, int b) {
		return gcd02(a, b);
	}

	/**
	 * 一般方法
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private int gcd01(int a, int b) {
		int result = 1;
		int min = (a < b) ? a : b;
		for (int i = 1; i <= min; i++) {
			if (a % i == 0 && b % i == 0) {
				result = i;
			}
		}
		return result;
	}

	/**
	 * 辗转相除法
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private int gcd02(int a, int b) {
		int max = (a >= b) ? a : b;
		int min = (a < b) ? a : b;
		int result = max;
		if (min > 0) {
			result = gcd02(min, max % min);
		}
		return result;
	}

	/**
	 * 求两个数的最小公倍数
	 * 
	 * <pre>
	 * 如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，
	 * 对于两个整数来说，指该两数共有倍数中最小的一个。
	 * </pre>
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public int lcm(int a, int b) {
		return lcm02(a, b);
	}

	/**
	 * 依赖于 gcd
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public int lcm01(int a, int b) {
		int result = 0;
		int gcd = gcd(a, b);
		result = a * b / gcd;
		return result;
	}

	public int lcm02(int a, int b) {
		int max = (a >= b) ? a : b;
		int min = (a < b) ? a : b;
		int result = max;
		if (max % min > 0) {
			result = max * min * (max % min);
		}
		return result;
	}

	/**
	 * <pre>
	 * 质数又称素数。
	 * 指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
	 * 换句话说，只有两个正因数（1和自己）的自然数即为素数。
	 * 比1大但不是素数的数称为合数。
	 * 1和0既非素数也非合数。
	 * 合数是由若干个质数相乘而得到的。
	 * 所以，质数是合数的基础，没有质数就没有合数。
	 * 
	 * 质数的判断：
	 * 1：只能被1和本身整除。
	 * 或
	 * 2：不能被小于它的平方根的所有质数整除就是质数。
	 * </pre>
	 * 
	 * @param n
	 * @return
	 */
	public boolean isPrime(int n) {
		boolean flag = true;
		int tmp = (int) Math.sqrt(n) + 1;
		for (int i = 2; i < tmp; i++) {
			if (n % i == 0) {
				flag = false;
			}
		}

		return flag;
	}
}
